package com.java_foundation.base_demo.test_3;

import org.junit.Test;

/**
 * @program: java_foundation
 * @description: 有n步台阶，一次只能上1步或2步，共有多少种走法？
 * @author: xiongbangwen <Email>xiongbangwen@163.com</Email>
 * @create: 2020-05-31 01:13
 **/
public class StepAlgorithm {
    //递归实现，简洁，但是当数据量大的时候效率低
    public int fun(int n){
        if (n < 1) {
          throw new IllegalArgumentException("不能小于1");
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return fun(n-2) + fun(n-1);
    }
    //循环实现
    public int loop(int n){
        if (n < 1) {
            throw new IllegalArgumentException("不能小于1");
        }
        if (n == 1 || n == 2) {
            return n;
        }

        int two = 2;//初始化为走到第二级的走法
        int one = 1;//初始化为走到第1级的走法
        int sum = 0;

        for (int i = 3;i<=n;i++){
            //最后跨2步 + 最后跨一步的算法
            sum = one + two;
            one = two;
            two = sum;
        }
        return sum;
    }

    @Test
    public void test(){
        long startTime = System.currentTimeMillis();
        System.out.println(fun(40));//165580141
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);//338
    }
    @Test
    public void test1(){
        long startTime = System.currentTimeMillis();
        System.out.println(loop(40));//1318412525
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);//0
    }
}
